Given an integer array nums which is sorted in ascending order and all of its elements are unique and given also an integer k, return the kth missing number starting from the leftmost number of the array.
Example 1:
Input: nums = [4,7,9,10], k = 1 Output: 5 Explanation: The first missing number is 5.
Example 2:
Input: nums = [4,7,9,10], k = 3 Output: 8 Explanation: The missing numbers are [5,6,8,...], hence the third missing number is 8.
Example 3:
Input: nums = [1,2,4], k = 3 Output: 6 Explanation: The missing numbers are [3,5,6,7,...], hence the third missing number is 6.
Constraints:
1 <= nums.length <= 5 * 1041 <= nums[i] <= 107numsis sorted in ascending order, and all the elements are unique.1 <= k <= 108
Follow up: Can you find a logarithmic time complexity (i.e.,
O(log(n))) solution?Average Rating: 3.57 (49 votes)
Solution
Approach 1: One Pass
Intuition
The problem is similar to First Missing Positive and the naive idea would be to solve it in a similar way by one pass approach.
Let's first assume that one has a function missing(idx)
that returns how many numbers are missing until the element
at index idx.
With the help of such a function the solution is straightforward :
-
Find an index such that
missing(idx - 1) < k <= missing(idx). In other words, that means that kth missing number is in-betweennums[idx - 1]andnums[idx].One even could compute a difference between kth missing number and
nums[idx - 1]. First, there aremissing(idx - 1)missing numbers untilnums[idx - 1]. Second, allk - missing(idx - 1)missing numbers fromnums[idx - 1]to kth missing are consecutive ones, because all of them are less thannums[idx]and hence there is nothing to separate them. Together that means that kth smallest is larger thannums[idx - 1]byk - missing(idx - 1). -
Return kth smallest
nums[idx - 1] + k - missing(idx - 1).
The last thing to discuss is how to implement
missing(idx)function.
Let's consider an array element at index idx. If there is no numbers
missing, the element should be equal to nums[idx] = nums[0] + idx.
If k numbers are missing, the element should be equal to
nums[idx] = nums[0] + idx + k.
Hence the number of missing elements is equal to
nums[idx] - nums[0] - idx.
Algorithm
-
Implement
missing(idx)function that returns how many numbers are missing until array element with indexidx. Function returnsnums[idx] - nums[0] - idx. -
Find an index such that
missing(idx - 1) < k <= missing(idx)by a linear search. -
Return kth smallest
nums[idx - 1] + k - missing(idx - 1).
Implementation
Complexity Analysis
-
Time complexity: O(N) since in the worst case it's one pass along the array.
-
Space complexity: O(1) since it's a constant space solution.
Approach 2: Binary Search
Intuition
Approach 1 uses the linear search and doesn't profit from the fact that array is sorted. One could replace the linear search by a binary one and reduce the time complexity from O(N) down to O(logN).
The idea is to find the leftmost element such that the number of missing numbers until this element is less or equal to k.
Algorithm
-
Implement
missing(idx)function that returns how many numbers are missing until array element with indexidx. Function returnsnums[idx] - nums[0] - idx. -
Find an index such that
missing(idx - 1) < k <= missing(idx)by a binary search. -
Return kth smallest
nums[idx - 1] + k - missing(idx - 1).
Implementation
Complexity Analysis
-
Time complexity: O(logN) since it's a binary search algorithm in the worst case when the missing number is less than the last element of the array.
-
Space complexity : O(1) since it's a constant space solution.
Last Edit: June 29, 2020 6:04 PM
approach one solution was made like a rocket science while a simple for loop could just do the job:
class Solution {
public:
int missingElement(vector<int>& nums, int k) {
int n=nums.size(),diff=0;
for(int i=1;i<n;i++)
{
diff=nums[i]-nums[i-1]-1;
if(diff>=k) return nums[i-1]+k;
k-=diff;
}
return nums[n-1]+k;
}
};
I think using the phrase that approach 1 "doesn't profit from the fact that array is sorted." is wrong. If the array wasnt sorted we would not be able to find what numbers were missing?
July 29, 2019 7:06 AM
the time complexity is not constant, you should only put for the worst case here.
July 5, 2020 10:09 PM
This question should be marked hard.
August 12, 2019 5:55 AM
The constant complexity is very misleading (or over simplified) here.
November 16, 2019 10:25 AM
The idea is to find the leftmost element such that the number of missing numbers until this element is smaller or equal to k.
should be greater
Was asked this question in my Facebook onsite interview, 2nd question after I completed the first one in under 20 min, took a long time to arrive at the binary search solution with the help of the interviewer, but didn't have time in the end to code it all. If you haven't seen this question before, it is very difficult to see that binary search pattern especially in an interview setting.
July 14, 2020 11:16 PM
What is the intuition behind nums[idx - 1] + k - missing(idx - 1)?
Last Edit: December 20, 2019 7:51 PM
Time Complexity is calculated by taking the worst-case into account. Saying that it is O(1) is extremely misleading for a lot of people. Please change it!
You don't have any submissions yet.
xxxxxxxxxxclass Solution {public: int missingElement(vector<int>& nums, int k) { }};


